#include <iostream>
#include <queue>
#include <vector>

using std::cout;
using std::endl;
using std::priority_queue;
using std::vector;

void test()
{
/*  
    template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
    > class priority_queue;

    T：表示优先级队列中存储的元素类型。
    
    Container：表示存储元素的底层容器类型，默认为std::vector<T>。
    优先级队列使用这个容器来存储元素，并利用容器的特性来实现优先级队列的功能。
    
    Compare：表示比较元素大小的函数对象类型，默认为std::less<typename Container::value_type>。
    这个函数对象用于确定元素的优先级顺序，默认情况下使用std::less来进行比较。

    value_type 是 C++ 标准库中容器类型定义的一个内部类型。它表示容器中存储的元素的类型。
    每种标准容器都定义了 value_type，以便用户可以方便地了解容器中存储的元素类型。
    例如，对于 vector<int>，value_type 就是 int；
    对于 list<double>，value_type 就是 double。
    在优先级队列中，typename Container::value_type 表示底层容器中存储的元素类型，
    通过这种方式，可以方便地获取和使用容器中元素的类型，而不需要显式地指定。
    T和value_type一个意思，后者更具有通用性

=========================================================================

    优先级队列的底层使用的是堆排序,默认使用的是大根堆
    原理：当有新的元素插入进来的时候，会与堆顶进行比较，
    如果堆顶比新插入的元素要小，满足std::less，true
    就将新的元素与上一次的堆顶进行置换，也就是新的元素会成为新的堆顶;
    如果新插入的元素比堆顶要小，也就是不满足std::less,那么堆顶不变
 
    总之，使用less，当前堆顶<新插入为true，下落，得到大根堆。greater得到小根堆
    大根堆\小根堆，在物理地址上都是数组

    虽然每次插入新元素可能会导致元素的储存顺序改变，但由于堆的性质，
    堆操作的时间复杂度是相对较低的（通常是对数级别），因此在大多数情况下，这种开销是可以接受的。
    虽然在某些情况下，插入元素可能导致内存重新分配和元素移动，但由于堆排序的特性，
    这种操作并不会导致所有元素都需要移动，比如通过下标访问直接交换元素，而不是和insert一样一个个移动
    通常情况下，堆操作会使得新元素上浮或下沉到正确的位置，而不会涉及整个容器的元素移动。
*/

    vector<int> vec = {1, 3, 6, 9, 8, 3, 6, 5};
    //vector<int> vec = {1, 3, 9, 5, 7};
    // priority_queue<int> pque(vec.begin(), vec.end());    //默认大根堆
    priority_queue<int> pque;
    //priority_queue<int, vector<int>, std::greater<int>> pque;   //小根堆

    for(size_t idx = 0; idx !=  vec.size(); ++idx)
    {
        pque.push(vec[idx]);
        cout << "优先级最高的元素 " << pque.top() << endl;
    }

    while(!pque.empty())
    {
        cout << pque.top() << "  ";
        pque.pop();
        if(!pque.empty())
            cout << pque.top() << "  ";
    }
    cout << endl;
}

int main()
{
    test();
    return 0;
}


